package com.linyaonan.leetcode.medium._116;

import javax.lang.model.element.VariableElement;
import java.util.LinkedList;

/**
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        LinkedList<Node> list = new LinkedList<>();
        list.addLast(root);
        addNext(list);
        return root;
    }

    public void addNext(LinkedList<Node> list) {
        int ceng = 1;
        int count = 0;
        Node first = null;
        while (!list.isEmpty()) {
            Node top = list.removeFirst();
            if (first == null) {
                first = top;
            } else {
                first.next = top;
                first = first.next;
            }

            if (--ceng == 0) {
                count++;
                ceng = 1 << count;
                first = null;
            }

            if (top.left != null) {
                list.addLast(top.left);
            }
            if (top.right != null) {
                list.addLast(top.right);
            }


        }

    }
}